A kd-tree (short for k-dimensional tree) is a well-known space-partitioning data structure for organizing points in k-dimensional space. As an acceleration structure, kd-trees have been used in a variety of graphics applications.
Because of its significant usage in graphics, fast kd-tree construction has been a subject of much interest in recent years, with several CPU-based algorithms proposed and/or implemented. With a kd-tree, for example, a dynamic scene can be rendered, including by photon mapping, in which rays from a light source and a camera are traced until they terminate, at which time they are combined to produce radiance values. Photon mapping is useful in commercial modeling and rendering software, but is computationally slow and thus not very practical in an interactive model to dynamically render frequently changing scenes.